/*
* 41. 缺失的第一个正数
* 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
* 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
* */

// 方法一
/*const firstMissingPositive = function(nums) {
  nums = nums.filter(item => item > 0)
  const len = nums.length

  if (len) {
    nums.sort((a, b) => a - b)

    if (nums[0] !== 1) {
      return 1
    } else {
      for (let i = 0; i < len - 1; i++) {
        if (nums[i + 1] - nums[i] > 1) {
          return nums[i] + 1
        }
      }
      return nums[len - 1] + 1
    }
  } else {
    return 1
  }
}*/

const firstMissingPositive = (nums) => {
  nums = nums.filter(item => item > 0)

  const len = nums.length

  for (let i = 0; i < len; i++) {
    let minIndex = i

    for (let j = i + 1; j < len; j++) {
      if (nums[minIndex] > nums[j]) {
        minIndex = j
      }
    }

    let tmp = nums[i]
    nums[i] = nums[minIndex]
    nums[minIndex] = tmp

    if (i > 0) {
      if (nums[i] - nums[i - 1] > 1) {
        return nums[i - 1] + 1
      }
    } else {
      if (nums[0] !== 1) {
        return 1
      }
    }
  }
  return len ? nums[len - 1] + 1 : 1
}

export default firstMissingPositive
